-- 2022-8-10

---[[ 图形

    -- 像其他现代编程语言一样 Lua语言也允许开发人员使用多种实现表示图 每种实现都有其适用的特定算法
    -- 这里 我们接下来将介绍一种简单的面向对象的实现方式 在这种实现中适应对象来表示节点(实际上是表) 将边(arc)表示为节点之间的引用

    -- 我们使用一个由两个字段组成的表来表示每个节点 即name(节点的名称)和adj(与此节点邻近的节点集合)
    -- 由于我们会从一个文本文件中加载图对应的数据 使用需要能够根据节点的名称来寻找指定节点的方法
    -- 因此 我们使用了一个额外的表来建立节点和节点名称之间的映射
    -- 函数name2node可以根据指定节点的名称返回对应的节点:
    local function name2node (graph,name)
        local node = graph[name]
        if not node then
            -- 节点不存在 创建一个新节点
            node = {name = name,adj = {}}
            graph[name] = node
        end
        return node
    end
    -- 从文件中加载图
    function readgraph()
        local graph = {}
        for line in io.lines do
            -- 把一行分割为两个名字
            local namefrom,nameto = string.match(line,"(%S+)%s+(%S+)")
            -- 找到对应的节点
            local from = name2node(graph,namefrom)
            local to = name2node(graph,nameto)
            -- 把'to'增加到邻接集合'from'中
            from.adj[to] = true
        end
        return graph
    end
    -- 该函数逐行的读取一个文件 文件的每一行中有两个节点的名称 表示从第一个节点到第二个节点有一条边
    -- 对于每一个 调用函数string.match将一行中的两个节点的名称分开 然后根据名称找到对应的节点(如果需要的话创建节点) 最后将这些节点连接在一起

    -- 寻找两个节点之间的路径
    function findpath (curr,to,path,visited)
        path = path or {}
        visited = visited or {}
        if visited[curr] then -- 是否节点已被访问？
            return nil        -- 不存在路径
        end
        visited[curr] = true  -- 标记节点为已被访问
        path[#path+1] = curr  -- 增加到路径中
        if curr == to then    -- 是否是最后一个节点
            return path
        end
        -- 尝试所有的邻接节点
        for node in pairs(curr.adj) do
            local p = findpath(node,to,path,visited)
            if p then
                return p
            end
        end
        table.remove(path)
    end
    -- 函数findpath使用深度优先遍历搜索两个节点之间的路径
    -- 该函数的第一个参数是当前节点 第二个参数是目标节点 第三个参数用于保存从起点到当前节点的路径 最后一个参数为所有已被访问节点的集合(用于避免回路)
    -- 请读者注意分析该算法是如何不通过节点名称而直接对节点进行操作的
    -- 例如 visited 是一个节点的集合 而不是节点名称的集合 类似的 path也是一个节点的列表
    -- 为了测试上述代码 我们编写一个打印一条路径的函数 再编写一些代码让上述所有代码跑起来
    function printpath(path)
        for i = 1 , #path do
            print(path[i].name)
        end
    end

    local g = readgraph()
    local a = name2node(g,"a")
    local b = name2node(g,"b")
    local p = findpath(a,b)
    if p then
        printpath(p)
    end
--]]